package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-05-06 09:17
 */
public class CA1288删除被覆盖的区间 {

    public static void main(String[] args) {

        int[][] intervals = {{11768, 31448}, {16159, 85133}, {21472, 36144}, {16618, 30065}, {4576, 36408}, {7724, 64130}, {1266, 3860}, {58048, 86441}, {92674, 97189}, {51780, 65166}, {39007, 57135}, {40706, 41738}, {17376, 39394}, {34630, 91403}, {9709, 60799}, {85831, 87397}, {43485, 89583}, {36441, 91991}, {27475, 89118}, {8596, 15334}, {39173, 93544}, {32847, 48569}, {30766, 75571}, {12766, 41340}, {3987, 27565}, {66314, 85926}, {18328, 96793}, {25172, 26705}, {15784, 76956}, {14284, 79051}, {48447, 79987}, {19738, 76133}, {31308, 45731}, {19428, 28254}, {22823, 52333}, {35230, 37343}, {67953, 84789}, {76248, 86702}, {5110, 96422}, {20587, 74505}, {47815, 95709}, {46430, 82622}, {183, 20347}, {53105, 56072}, {44674, 46474}, {37239, 49796}, {35704, 46808}, {37184, 67180}, {38822, 57041}, {2181, 99742}, {36083, 40434}, {52650, 88740}, {4291, 28657}, {8095, 85599}, {18276, 89086}, {81696, 87386}, {12903, 83504}, {48484, 82504}, {28319, 41844}, {15792, 16711}, {82982, 96338}, {26903, 66836}, {50766, 58665}, {32462, 91941}, {26912, 68207}, {1305, 23010}, {70695, 99690}, {28970, 43658}, {26895, 80550}, {74980, 90288}, {7913, 90977}, {24815, 38571}, {63697, 71036}, {9337, 94457}, {33171, 99065}, {16262, 52863}, {472, 20078}, {41908, 61801}, {73389, 76368}, {89178, 93806}, {19217, 95412}, {16732, 81467}, {30041, 64951}, {33918, 40516}, {74641, 86542}, {79579, 79743}, {17472, 21371}, {12766, 13516}, {57027, 74444}, {2204, 63111}, {28984, 33075}, {59655, 82499}, {18268, 41537}, {27687, 73270}, {8919, 13116}, {87707, 87901}, {64483, 96888}, {42413, 89448}, {9576, 74545}, {14899, 33676}, {8427, 8967}, {20193, 43369}, {28729, 86123}, {7563, 23699}, {52063, 72524}, {34650, 53675}, {9628, 57735}, {14015, 18125}, {43864, 66090}, {32136, 66037}, {11633, 23591}, {45502, 65919}, {1854, 41646}, {50702, 69575}, {2714, 24191}, {40315, 54224}, {83721, 94610}, {63459, 79161}, {53954, 99571}, {3546, 42850}, {77614, 99895}, {73407, 86310}, {13279, 32591}, {37545, 84791}, {17417, 93069}, {45513, 73503}, {72722, 84459}, {40901, 95042}, {81933, 90319}, {24919, 38898}, {61229, 71419}, {12890, 20660}, {47340, 60190}, {28976, 79712}, {60544, 96219}, {10600, 67913}, {6788, 64110}, {61263, 87000}, {25754, 46778}, {30420, 66289}, {1354, 54947}, {2056, 94579}, {38169, 51660}, {12596, 85456}, {8466, 95393}, {53754, 54743}, {9039, 70041}, {43955, 84001}, {8806, 81615}, {26564, 50144}, {4511, 64830}, {47161, 75783}, {26736, 65558}, {29709, 70225}, {45489, 46989}, {31518, 44792}, {51423, 52654}, {53214, 69790}, {31396, 49525}, {85635, 86919}, {54282, 69532}, {64494, 97863}, {66058, 73331}, {75237, 76142}, {48048, 81536}, {36274, 91076}, {14172, 43387}, {56625, 79348}, {54159, 82643}, {3399, 70830}, {3816, 46845}, {28138, 63312}, {866, 75332}, {41592, 97568}, {29347, 72446}, {55497, 85575}, {9487, 51793}, {30935, 63172}, {1179, 19284}, {20500, 27393}, {22029, 91586}, {30700, 41374}, {22044, 64453}, {51503, 54915}, {45563, 72363}, {5396, 74241}, {51425, 60375}, {30028, 97113}, {4997, 79377}, {37664, 61662}, {13375, 38568}, {3794, 98836}, {5432, 40944}, {26705, 70217}, {803, 30730}, {21028, 30005}, {45886, 54421}, {43573, 51675}, {75024, 92666}, {41653, 83478}, {33555, 66848}, {49181, 93739}, {4163, 86623}, {52931, 62062}, {41629, 54914}, {24768, 57074}, {37558, 63119}, {43125, 98047}, {42016, 70315}, {9270, 48913}, {47233, 75413}, {1164, 20714}, {58562, 88213}, {38974, 70379}, {14056, 46247}, {1263, 67821}, {13649, 36772}, {74865, 90685}, {6525, 87559}, {27905, 28299}, {6561, 29534}, {51822, 69237}, {85180, 91037}, {3401, 53676}, {25087, 70035}, {30258, 34956}, {24266, 87933}, {26802, 43667}, {37324, 86317}, {16697, 33065}, {35317, 68724}, {59340, 80084}, {64645, 81036}, {15381, 91094}, {5115, 93359}, {38202, 41333}, {58480, 66620}, {15915, 77228}, {14040, 57579}, {22168, 85669}, {61653, 70226}, {73459, 74108}, {8872, 50720}, {57501, 77240}, {29151, 32975}, {52727, 88777}, {25523, 34264}, {96360, 98053}, {37956, 67587}, {32503, 53545}, {24394, 90787}, {8578, 41100}, {36773, 91640}, {16706, 39331}, {60238, 94051}, {1737, 43141}, {5676, 75323}, {42796, 99515}, {15413, 89746}, {16593, 83730}, {23217, 62351}, {843, 71177}, {13406, 36884}, {20716, 94944}, {49266, 76033}, {13618, 90581}, {36906, 74958}, {54255, 93176}, {822, 4470}, {5169, 55835}, {4645, 83937}, {64759, 72647}, {74915, 97288}, {13945, 31268}, {45604, 64950}, {39443, 43333}, {43432, 99707}, {3496, 31704}, {83661, 97269}, {2134, 50298}, {24334, 71126}, {10752, 60243}, {1438, 25061}, {18516, 72307}, {9460, 78743}, {27242, 92739}, {23964, 50854}, {37047, 63587}, {36978, 93079}, {58596, 63823}, {2879, 59551}, {14838, 41768}, {76713, 93307}, {38963, 42464}, {22206, 55276}, {11428, 25788}, {7025, 88757}, {8323, 84819}, {36366, 74594}, {41230, 98613}, {7050, 46051}, {8412, 32418}, {27172, 90363}, {17949, 71236}, {82064, 93294}, {33925, 73972}, {35681, 61576}, {76349, 84503}, {82817, 90360}, {9316, 96894}, {66173, 76415}, {89984, 93838}, {33953, 35394}, {33511, 69181}, {82376, 94564}, {78397, 82059}, {46315, 52110}, {39067, 46711}, {9860, 58923}, {50059, 94916}, {39984, 53220}, {57465, 76559}, {50240, 73922}, {32687, 58702}, {73808, 78444}, {19949, 41019}, {47213, 71089}, {58731, 75351}, {7985, 82734}, {41675, 81417}, {9113, 64550}, {20261, 94338}, {53667, 93769}, {17214, 65978}, {35515, 63350}, {43052, 85235}, {69733, 89621}, {63803, 70549}, {30674, 80482}, {20937, 86027}, {2402, 84423}, {12730, 29646}, {12773, 77098}, {26098, 67750}, {10092, 58190}, {52296, 68044}, {24670, 90549}, {24482, 99323}, {7373, 84698}, {70832, 87649}, {36035, 42462}, {37853, 89033}, {38518, 84429}, {7888, 70250}, {42362, 55841}, {53917, 79056}, {86879, 87679}, {33524, 69912}, {11139, 43648}, {33265, 49733}, {23760, 26351}, {50268, 78182}, {49814, 55332}, {9791, 80113}, {39151, 54222}, {52486, 56557}, {20845, 85353}, {63203, 75991}, {1289, 15047}, {71518, 93594}, {24034, 83802}, {40716, 97914}, {41476, 88152}, {30276, 89860}, {51687, 77041}, {25886, 92273}, {17179, 64533}, {25570, 97010}, {24416, 70495}, {32794, 56011}, {14248, 26420}, {1491, 30556}, {68057, 72826}, {58032, 75143}, {155, 57466}, {72695, 96173}, {64035, 90432}, {63209, 66501}, {64054, 89009}, {4866, 71978}, {21315, 26876}, {9665, 66334}, {31491, 69394}, {49410, 63592}, {42533, 69769}, {21867, 87593}, {75123, 87154}, {11059, 83509}, {54377, 91553}, {16389, 94485}, {4007, 46638}, {62558, 98768}, {47366, 73620}, {76429, 91860}, {863, 94167}, {9354, 47847}, {4879, 26482}, {12445, 52886}, {42131, 72374}, {42502, 86823}, {914, 38456}, {32547, 62361}, {3078, 20170}, {9384, 84322}, {10206, 26329}, {23486, 83258}, {23231, 57068}, {29697, 47626}, {40552, 93098}, {17806, 24968}, {28107, 51239}, {10946, 21182}, {48092, 61608}, {15908, 58992}, {7601, 59813}, {38631, 74491}, {77178, 86115}, {30566, 59872}, {20128, 85840}, {68073, 77186}, {87460, 94592}, {8308, 16785}, {52767, 79259}, {34456, 51314}, {4666, 74623}, {45889, 88140}, {41417, 77282}, {42952, 89266}, {24258, 66031}, {5971, 11291}, {2661, 7699}, {17161, 71259}, {11396, 76651}, {1955, 85098}, {9363, 67513}, {53084, 55744}, {2868, 53313}, {48435, 83013}, {35461, 93054}, {71194, 95432}, {23828, 46076}, {34513, 77616}, {14651, 99564}, {18517, 60080}, {60929, 75730}, {33372, 45428}, {54831, 88378}, {14125, 42922}, {8223, 8648}, {9765, 55149}, {9153, 98632}, {67496, 89120}, {34433, 69070}, {11694, 54778}, {35087, 69875}, {15374, 74396}, {21377, 56163}, {53583, 64742}, {44493, 80488}, {16114, 31213}, {45615, 74891}, {51357, 80679}, {2670, 73772}, {45754, 81063}, {39621, 44422}, {22940, 49588}, {11156, 17754}, {48466, 66191}, {80028, 86453}, {15211, 99519}, {19732, 42084}, {49261, 58480}, {71320, 97047}, {97576, 98831}, {7944, 70664}, {52492, 95677}, {78473, 98812}, {44927, 72838}, {17982, 23110}, {13627, 16936}, {62452, 92685}, {41692, 48103}, {57084, 97783}, {27459, 66841}, {5737, 24737}, {7336, 94585}, {60571, 77881}, {2290, 30785}, {36511, 44391}, {7798, 66841}, {60640, 65494}, {20163, 63465}, {18456, 32893}, {9443, 99070}, {67667, 87110}, {63831, 73257}, {6216, 84278}, {16590, 64041}, {10033, 49562}, {48025, 77751}, {70616, 99121}, {8568, 54861}, {57392, 68501}, {63804, 79871}, {37796, 65224}, {35442, 60509}, {6046, 48355}, {1798, 89355}, {48118, 54980}, {47527, 51958}, {58566, 83956}, {18459, 40087}, {40795, 66288}, {2965, 94740}, {50600, 89194}, {8712, 99559}, {20566, 76647}, {10676, 79569}, {63346, 68989}, {55200, 72936}, {82123, 85841}, {34855, 59891}, {60428, 77939}, {2935, 42745}, {14044, 57717}, {7221, 21425}, {38740, 71957}, {34151, 50122}, {49530, 69153}, {77625, 95308}, {4661, 23082}, {1918, 57713}, {32911, 91035}, {60691, 97494}, {54036, 82556}, {13961, 14569}, {32698, 48282}, {8675, 16629}, {75769, 98898}, {15468, 86869}, {49177, 60178}, {68141, 88581}, {32749, 84530}, {64708, 84703}, {982, 68090}, {88624, 93123}, {4954, 78480}, {46985, 95248}, {16269, 68543}, {27912, 49943}, {14291, 20649}, {43367, 85382}, {17004, 85248}, {54131, 96178}, {17193, 41646}, {33016, 58297}, {30612, 30730}, {68105, 99671}, {28526, 29719}, {47968, 88684}, {15539, 40775}, {42136, 59936}, {22780, 27044}, {23478, 58880}, {70121, 96342}, {10137, 23822}, {70420, 96815}, {39741, 72539}, {26913, 79196}, {62110, 87542}, {56406, 86886}, {30314, 62437}, {3231, 77080}, {43328, 95407}, {12391, 94144}, {38261, 79475}, {13174, 48909}, {9857, 40747}, {82982, 87022}, {97790, 98590}, {12740, 32873}, {42002, 44755}, {62636, 96767}, {13352, 32956}, {3522, 96510}, {28922, 92982}, {26825, 32490}, {37837, 80008}, {4994, 18615}, {68034, 81088}, {69863, 78341}, {5271, 90041}, {26482, 64106}, {6610, 31996}, {32262, 49129}, {33469, 48327}, {73706, 97334}, {42267, 42809}, {14614, 59404}, {1122, 75822}, {26910, 87758}, {10820, 65278}, {83002, 99326}, {7207, 39589}, {9806, 36461}, {35761, 98588}, {3781, 34795}, {46488, 53122}, {49895, 82979}, {38340, 89607}, {65728, 67636}, {10177, 16463}, {89608, 93966}, {18928, 19199}, {57099, 95084}, {60984, 94213}, {26893, 31685}, {24354, 41952}, {4498, 58254}, {2978, 42649}, {25069, 48358}, {11589, 78705}, {626, 75121}, {52609, 98974}, {40833, 49723}, {50510, 87275}, {2625, 85818}, {4916, 41950}, {34838, 54980}, {11853, 29305}, {20610, 28527}, {94457, 98706}, {26841, 80146}, {57412, 70480}, {39677, 86630}, {54781, 64725}, {286, 62614}, {12627, 83901}, {90759, 94638}, {4507, 59977}, {49713, 69633}, {83798, 86695}, {979, 25492}, {27580, 35430}, {56833, 72236}, {43705, 53472}, {14638, 80298}, {49432, 79657}, {51405, 84132}, {75102, 76634}, {30150, 65104}, {31969, 92419}, {8018, 36964}, {1820, 70590}, {25593, 71699}, {32634, 73181}, {89427, 98826}, {29124, 91728}, {17252, 86242}, {62044, 95535}, {9030, 16694}, {41425, 51266}, {22756, 99939}, {43621, 85643}, {53434, 86113}, {44586, 64419}, {3038, 8516}, {21997, 64973}, {68816, 86973}, {89541, 92552}, {926, 25657}, {1346, 93212}, {20964, 97818}, {20185, 37090}, {13426, 62135}, {83766, 87568}, {72131, 89858}, {39509, 82762}, {39883, 50574}, {82369, 87609}, {6315, 53912}, {2129, 72940}, {15666, 78904}, {39885, 90436}, {28628, 34668}, {56431, 56764}, {53719, 77233}, {7013, 35908}, {10641, 69200}, {2365, 76823}, {66022, 73994}, {8653, 90277}, {63210, 85682}, {34421, 69150}, {12022, 28995}, {17475, 89958}, {18024, 77913}, {18383, 37604}, {58014, 82064}, {65185, 87319}, {5126, 72535}, {31384, 68060}, {29747, 95426}, {5631, 35957}, {38646, 65347}, {2078, 82582}, {36165, 93547}, {22530, 40855}, {30214, 98072}, {14378, 19096}, {21587, 94808}, {45678, 89303}, {73978, 75869}, {49016, 60962}, {47137, 91049}, {5679, 50120}, {17457, 67220}, {51870, 85092}, {57194, 73993}, {52218, 58019}, {44715, 46006}, {62519, 97604}, {64049, 66922}, {44199, 91877}, {14118, 61044}, {61303, 89022}, {16476, 25233}, {40693, 52405}, {26488, 60831}, {17802, 51655}, {74692, 95692}, {4757, 22873}, {15661, 46679}, {56596, 67662}, {23264, 95546}, {7132, 95661}, {34119, 47101}, {10890, 56864}, {24131, 58891}, {12613, 90532}, {19883, 30865}, {7851, 63655}, {47459, 97435}, {4809, 59383}, {47229, 62860}, {17864, 78230}, {75461, 97152}, {3291, 94611}, {57755, 84429}, {79860, 85345}, {67418, 78711}, {14847, 31711}, {23955, 75816}, {14268, 50123}, {28287, 33741}, {30385, 47834}, {40634, 66294}, {63911, 82371}, {64809, 75660}, {4165, 22119}, {8974, 81909}, {42346, 48394}, {19552, 74052}, {47742, 77479}, {996, 93072}, {20467, 91878}, {74335, 82976}, {5672, 28624}, {25837, 50959}, {29747, 61155}, {21369, 53659}, {80852, 94049}, {8327, 57108}, {40735, 44038}, {41023, 71465}, {20694, 77984}, {34970, 97257}, {61327, 85020}, {10476, 12246}, {12524, 85260}, {52475, 74325}, {76301, 80419}, {3873, 56205}, {18216, 70570}, {92954, 96828}, {41767, 91736}, {1101, 10141}, {15963, 46987}, {62357, 93050}, {32796, 67215}, {76133, 98787}, {46478, 83486}, {47720, 92947}, {4744, 78083}, {7487, 54438}, {48834, 82872}, {55662, 76606}, {4597, 6846}, {39600, 57560}, {21703, 88616}, {25141, 33829}, {72565, 86180}, {11123, 38110}, {21484, 61917}, {23807, 52352}, {23458, 30330}, {39625, 91655}, {19094, 84816}, {57232, 97902}, {28566, 95140}, {9088, 89466}, {13580, 92161}, {41465, 98452}, {30077, 91458}, {17531, 84001}, {6292, 57846}, {29499, 84117}, {37493, 43599}, {41768, 92220}, {18565, 90519}, {4778, 78977}, {68813, 81332}, {17813, 20285}, {56908, 89159}, {20903, 66007}, {21704, 52634}, {21865, 86505}, {39731, 58957}, {36428, 40332}, {41153, 57023}, {66773, 88511}, {66291, 75463}, {12515, 91959}, {5294, 57324}, {74633, 99337}, {52102, 58166}, {25475, 30248}, {37600, 88258}, {5152, 64060}, {52728, 55873}, {1494, 92356}, {14003, 81121}, {52234, 72275}, {36582, 58451}, {57001, 60916}, {10039, 52182}, {20640, 85413}, {55952, 60555}, {65167, 90538}, {36848, 71375}, {22171, 24133}, {9802, 84742}, {56185, 75748}, {7098, 74533}, {36253, 87452}, {58996, 95017}, {5102, 59500}, {26600, 80260}, {37930, 54495}, {25710, 26369}, {3051, 37922}, {24582, 57698}, {31958, 96096}, {22525, 76769}, {25924, 35830}, {62770, 65072}, {185, 7814}, {45812, 97488}, {78149, 86264}, {29821, 82839}, {66261, 73866}, {95605, 97026}, {36620, 99083}, {96367, 99705}, {15745, 34689}, {29085, 96924}, {9885, 51045}, {22657, 64183}, {23677, 54554}, {26340, 62546}, {5082, 84042}, {30340, 98638}, {4669, 56062}, {89033, 93176}, {916, 87535}, {20844, 81958}, {86570, 96363}, {55954, 89024}, {41266, 89452}, {3600, 77617}, {50979, 80218}, {48160, 83599}, {57728, 97619}, {37883, 96971}, {23249, 74025}, {51407, 54821}, {45648, 93073}, {33943, 62017}, {37162, 68089}, {24574, 74063}, {1418, 6929}, {55656, 56884}, {27385, 67590}, {53470, 69923}, {18945, 54334}, {6132, 95790}, {5496, 59518}, {2214, 63435}, {11871, 95947}, {3516, 62897}, {9299, 23132}, {26791, 46891}, {23724, 62477}, {69419, 89688}, {41483, 56548}, {49284, 60117}, {80121, 86418}, {8259, 30742}, {28601, 32368}, {24490, 76536}, {21469, 75802}, {18084, 98291}, {62503, 89514}, {27984, 47378}, {5092, 17801}, {21353, 56327}, {54906, 86305}, {28659, 94659}, {4689, 70184}, {52270, 63114}, {30566, 62716}, {49157, 64660}, {37214, 99754}, {29049, 38282}, {23302, 43190}, {2181, 15512}, {42412, 95758}, {41073, 45607}, {9985, 22573}, {74693, 80899}, {51742, 56269}, {63359, 92931}, {49708, 65197}, {42652, 45046}, {51608, 60361}, {6941, 47775}, {72031, 75951}, {67959, 83214}, {13661, 18463}, {20035, 69816}, {36590, 50053}, {41252, 74421}, {21483, 44002}, {12760, 96603}, {62798, 72382}, {28174, 35660}, {3265, 25320}, {54750, 89437}, {19325, 55050}, {22049, 44312}, {31462, 44665}, {34887, 50006}, {26106, 94215}, {1535, 62327}, {54969, 95223}, {24522, 99341}, {86905, 89102}, {36574, 95434}, {49004, 62007}, {32209, 59789}, {75899, 95277}, {9657, 62753}, {25967, 42457}, {49091, 68208}, {39228, 45494}, {45025, 74673}, {20728, 57728}, {6460, 91852}, {22210, 29226}, {54306, 75889}, {39145, 97958}, {45343, 86811}, {32659, 37988}, {9317, 61375}, {30969, 35211}, {29812, 44609}, {54998, 93852}, {6639, 35447}, {32169, 86201}, {597, 99081}};
        System.out.println(removeCoveredItervals(intervals));
    }


    /**
     * 使用hashtree 对左边界值进行排序
     * 从小往大遍历 记录最大的右边界值 如果下一个值的右边界比最大值小 则删除下一个的值
     *
     * @param intervals
     * @return
     */
    public static int removeCoveredItervals(int[][] intervals) {

        Map<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < intervals.length; i++) {
            Integer value = map.get(intervals[i][0]);
            if(value == null){
                map.put(intervals[i][0], intervals[i][1]);
            }else if(intervals[i][1] > value){
                map.put(intervals[i][0], intervals[i][1]);
            }
        }


        int maxRight = 0;
        int total = 0;

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > maxRight) {
                System.out.println(entry.getKey() + "-" + entry.getValue());
                total++;
                maxRight = entry.getValue();
            }
        }
        return total;
    }


    public static int removeCoveredIntervals2(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // Sort by start point.
                // If two intervals share the same start point,
                // put the longer one to be the first.
                return o1[0] == o2[0] ? o2[1] - o1[1]: o1[0] - o2[0];
            }
        });

        int count = 0;
        int end, prev_end = 0;
        for (int[] curr : intervals) {
            end = curr[1];
            // if current interval is not covered
            // by the previous one
            if (prev_end < end) {
                System.out.println(prev_end);
                ++count;
                prev_end = end;
            }
        }
        return count;
    }
}
